home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / gc / GCreclaim.c,v < prev    next >
Text File  |  1991-06-17  |  28KB  |  971 lines
  1. head    1.1;
  2. access;
  3. symbols;
  4. locks; strict;
  5. comment    @ * @;
  6.  
  7.  
  8. 1.1
  9. date    91.06.17.23.20.31;    author boehm;    state Exp;
  10. branches;
  11. next    ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18. 1.1
  19. log
  20. @Initial revision
  21. @
  22. text
  23. @/* begincopyright
  24.   Copyright (c) 1988,1990 Xerox Corporation. All rights reserved.
  25.   Use and copying of this software and preparation of derivative works based
  26.   upon this software are permitted. Any distribution of this software or
  27.   derivative works must comply with all applicable United States export
  28.   control laws. This software is made available AS IS, and Xerox Corporation
  29.   makes no warranty about the software, its performance or its conformity to
  30.   any specification. Any person obtaining a copy of this software is requested
  31.   to send their name and post office or electronic mail address to:
  32.     PCR Coordinator
  33.     Xerox PARC
  34.     3333 Coyote Hill Rd.
  35.     Palo Alto, CA 94304
  36.     
  37.   Parts of this software were derived from code bearing the copyright notice:
  38.   
  39.   Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  40.   This material may be freely distributed, provided this notice is retained.
  41.   This material is provided as is, with no warranty expressed or implied.
  42.   Use at your own risk.
  43.   
  44.   endcopyright */
  45. #include "xr/GCPrivate.h"
  46. #include "xr/Threads.h"
  47.  
  48. #define I_HOLD_ML(ml) (((XR_ML)(ml))->ml_holder == XR_currThread)
  49.  
  50. #define DEBUG
  51. #undef DEBUG
  52.  
  53. /* Boehm, October 8, 1990 1:57:26 pm PDT */
  54.  
  55.  
  56.  
  57. /*
  58.  * reclaim phase
  59.  *
  60.  */
  61.  
  62. static long GC_last_gc_flushed = 0;
  63.  
  64. static struct hblk * GC_freeable_blocks = 0;
  65.     /* List of large object blocks waiting to be freed.  We enqueue these */
  66.     /* and then process them in large chunks.  Freeing a heap block can   */
  67.     /* be sufficiently expensive that we don't want to do this with the   */
  68.     /* world stopped. Processing them one at a time slows things down     */
  69.     /* because it causes the heap block allocator to lose some state.     */
  70.  
  71. /* Free some or all blocks on list of freeable blocks. Caller should hold */
  72. /* GC_allocate_ml.                               */
  73. static GC_free_blocks(how_many)
  74. long how_many;
  75. # define ALL 1000000000
  76. # define A_FEW 10
  77. {
  78.     register int i;
  79.     register struct hblk * h;
  80.     
  81.     if (!I_HOLD_ML(&GC_allocate_ml)) {
  82.         XR_Panic("GC_free_blocks 0");
  83.     }
  84.     for (i = 0; i < how_many; i++) {
  85.         if ((h = GC_freeable_blocks) == 0) return;
  86.         GC_freeable_blocks = hb_sz_link(h);
  87.         /* Mark it as being uninitialized */
  88.         hb_uninit(h) = 1;
  89.  
  90.     /* remove this block from list of active blocks */
  91.         GC_del_hblklist(h);  
  92.         
  93.     GC_freehblk(h);
  94.     }
  95. }
  96.     
  97. /* Assumes caller holds GC_allocate_ml */
  98. void GC_zero_reclaim_lists()
  99. {
  100.     register struct hblk ** hbpp;
  101.     register struct hblk ** rlp;
  102.     register struct hblk * hbp;
  103.     
  104.     for( rlp = reclaim_list; rlp < &reclaim_list[MAXOBJSZ+1]; rlp++ ) {
  105.       *rlp = (struct hblk *)0;
  106.     }
  107.     for( rlp = areclaim_list; rlp < &areclaim_list[MAXOBJSZ+1]; rlp++ ) {
  108.       *rlp = (struct hblk *)0;
  109.     }
  110.     GC_reclaim_inval_counter++;
  111. }
  112.  
  113. void GC_reclaim_empty_pages()
  114. /* Reclaim any potentially empty blocks that have not yet been     */
  115. /* reclaimed.                               */
  116. /* Caller should hold GC_allocate_ml.                   */
  117. {
  118.     register struct hblk ** hbpp;
  119.     register struct hblk ** rlp;
  120.     register struct hblk * hbp;
  121. #   ifdef PRINTSTATS
  122.     register long n_reclaimed = 0;
  123.     register long n_tenured = 0;
  124. #   endif
  125.  
  126.     if (!I_HOLD_ML(&GC_allocate_ml)) {
  127.         XR_Panic("GC_reclaim_empty_pages 0");
  128.     }
  129.     GC_free_blocks(ALL);
  130.     if (GC_gc_no == GC_last_gc_flushed) {
  131.     return;
  132.     }
  133.  
  134.     /* First blocks with composite objects: */
  135.       for( rlp = reclaim_list; rlp < &reclaim_list[MAXOBJSZ+1]; rlp++ ) {
  136.      hbpp = rlp;
  137.     while ((hbp = *hbpp) != (struct hblk *)0) {
  138.         if (GC_hblk_empty(hbp)) {
  139. #               ifdef PRINTSTATS
  140.             n_reclaimed++;
  141. #               endif
  142.         * hbpp = hb_sz_link(hbp);
  143.         GC_reclaim_entire_block(hbp);
  144.         } else {
  145.         hbpp = & (hb_sz_link(hbp));
  146. #               ifdef PRINTSTATS
  147.             n_tenured++;
  148. #               endif
  149.         }
  150.     }
  151.       }
  152.  
  153.     /* Now blocks with atomic objects: */
  154.       for( rlp = areclaim_list; rlp < &areclaim_list[MAXOBJSZ+1]; rlp++ ) {
  155.     hbpp = rlp;
  156.     while ((hbp = *hbpp) != (struct hblk *)0) {
  157.        if (GC_hblk_empty(hbp)) {
  158. #               ifdef PRINTSTATS
  159.             n_reclaimed++;
  160. #               endif
  161.         * hbpp = hb_sz_link(hbp);
  162.         GC_reclaim_entire_block(hbp);
  163.         } else {
  164.         hbpp = & (hb_sz_link(hbp));
  165. #               ifdef PRINTSTATS
  166.             n_tenured++;
  167. #               endif
  168.         }
  169.     }
  170.       }
  171.  
  172.     GC_last_gc_flushed = GC_gc_no;
  173.  
  174. #   ifdef PRINTSTATS
  175.         GC_vprintf(
  176.        "Reclaimed %d apparently empty blocks, skipped %d nonempty blocks\n",
  177.        n_reclaimed, n_tenured);
  178. #   endif
  179. }
  180.  
  181. /*
  182.  * Reclaim all pages that were reclaimed in the last collection cycle.
  183.  * Flush the rest.
  184.  *
  185.  * GC_allocate_ml should not be held by the caller.  However,
  186.  * we will acquire and release it repeatedly.
  187.  * We claim that we don't need the allocation lock for most of this,
  188.  * since GC_reclaim_composite and GC_reclaim_atomic are robust
  189.  * against being called on an empty list, and we don't write to any
  190.  * important data structures.  Thus we can't screw up in any
  191.  * way that would affect correctness (other than of printed
  192.  * statistics).  We do guarantee that all reclaim lists are
  193.  * empty when we're done, since no other thread will be adding
  194.  * to the lists.
  195.  */
  196. void GC_reclaim_useful_pages()
  197. {
  198.     register struct hblk ** hbpp;
  199.     register struct hblk * hbp;
  200.     register struct hblk ** rlp;
  201. #   ifdef PRINTSTATS
  202.     register long n_reclaimed = 0;
  203.     register long n_tenured = 0;
  204. #   endif
  205.  
  206.     if (I_HOLD_ML(&GC_allocate_ml)) {
  207.         XR_Panic("GC_reclaim_useful_pages 0");
  208.     }
  209.     /* First blocks with composite objects: */
  210.       for( rlp = reclaim_list; rlp < &reclaim_list[MAXOBJSZ+1]; rlp++ ) {
  211.     while ((hbp = *rlp) != (struct hblk *)0) {
  212.         if (hb_last_reclaimed(hbp) == GC_gc_no-1
  213.             || GC_hblk_empty(hbp)) {
  214. #               ifdef PRINTSTATS
  215.             n_reclaimed++;
  216. #               endif
  217.         GC_reclaim_composite(rlp);
  218.         } else {
  219. #               ifdef PRINTSTATS
  220.             n_tenured++;
  221. #               endif
  222.         XR_MonitorEntry(&GC_allocate_ml);
  223.         *rlp = hb_sz_link(hbp);
  224.         XR_MonitorExit(&GC_allocate_ml);
  225.         }
  226.     }
  227.       }
  228.  
  229.     /* Now blocks with atomic objects: */
  230.       for( rlp = areclaim_list; rlp < &areclaim_list[MAXOBJSZ+1]; rlp++ ) {
  231.     hbpp = rlp;
  232.     while ((hbp = *rlp) != (struct hblk *)0) {
  233.        if (hb_last_reclaimed(hbp) == GC_gc_no-1
  234.            || GC_hblk_empty(hbp)) {
  235. #               ifdef PRINTSTATS
  236.             n_reclaimed++;
  237. #               endif
  238.         GC_reclaim_atomic(rlp);
  239.         } else {
  240. #               ifdef PRINTSTATS
  241.             n_tenured++;
  242. #               endif
  243.         XR_MonitorEntry(&GC_allocate_ml);
  244.         *rlp = hb_sz_link(hbp);
  245.         XR_MonitorExit(&GC_allocate_ml);
  246.         }
  247.     }
  248.       }
  249.  
  250.     XR_MonitorEntry(&GC_allocate_ml);
  251.     GC_last_gc_flushed = GC_gc_no;
  252.     GC_reclaim_inval_counter++;
  253.     XR_MonitorExit(&GC_allocate_ml);
  254.  
  255.     GC_vprintf( "Reclaimed %d new blocks, flushed %d old blocks\n",
  256.            n_reclaimed, n_tenured);
  257. }
  258.  
  259.  
  260. /*
  261.  * The main routine for the sweep phase
  262.  */
  263.  
  264. void GC_clear_free_lists()
  265. {
  266.   /* Clear all free lists */
  267.   register struct obj **fop;
  268.   
  269.   for( fop = objfreelist; fop < &objfreelist[MAXOBJSZ+1]; fop++ ) {
  270.     *fop = (struct obj *)0;
  271.   }
  272.   for( fop = aobjfreelist; fop < &aobjfreelist[MAXOBJSZ+1]; fop++ ) {
  273.     *fop = (struct obj *)0;
  274.   }
  275. }
  276.  
  277. void GC_reclaim()
  278. {
  279. register struct hblk *hbp;    /* ptr to current heap block        */
  280. register unsigned long index;
  281. # ifdef SEPARATE_HEADERS
  282.     struct hblkhdr * hhdr;
  283. # endif
  284. register int sz;        /* size of objects in current block    */
  285. register bool is_atomic;        /* => current block contains ptrfree objs */
  286. register char * GC_heapstart_reg = GC_heapstart;
  287. # define GC_heapstart GC_heapstart_reg
  288. # ifdef PRINTSTATS
  289.     long now_count = 0;
  290.     long defer_count = 0;
  291.     long skip_count = 0;
  292. # endif
  293.  
  294.  
  295. #   ifdef PRINTBLOCKS
  296.         GC_vprintf("reclaim: current block sizes:\n");
  297. #   endif
  298.  
  299. #   ifdef DEBUG
  300.     GC_vprintf("GC_heapstart = 0x%X, GC_heaplim = 0x%X\n", GC_heapstart,
  301.            GC_heaplim);
  302.     { int i;
  303.       for (i = 0;
  304.            i < ((long)GC_heaplim - (long)GC_heapstart) / HBLKSIZE;
  305.            i++) {
  306.           GC_vprintf("(%d)", hblkmap[i]);
  307.       }
  308.       GC_vprintf("\n");
  309.     }
  310. #   endif
  311.  
  312.   /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
  313.   /* For blocks containing small objects, we queue the block for later     */
  314.   /* reclamation.                                                          */
  315.     hbp = (struct hblk *) (((long) GC_heaplim - 1) & ~(HBLKMASK-1));
  316.     index = hbp - (struct hblk *) GC_heapstart;
  317.     while (index > 0) {
  318.       switch (hblkmap[index]) {
  319.         case HBLK_INVALID:
  320.           index--;
  321.           break;
  322.         case HBLK_VALID:
  323.           hbp = ((struct hblk *) GC_heapstart) + index;
  324. #      ifdef SEPARATE_HEADERS
  325.         hhdr = headers[index];
  326.         sz = hb_sz_from_hdr(hhdr);
  327. #        define SZ_LINK hb_sz_link_from_hdr(hhdr)
  328. #      else
  329.         sz = hb_sz(hbp);
  330. #        define SZ_LINK hb_sz_link(hbp)
  331. #      endif
  332.       if (sz < 0) {
  333.         sz = -sz;
  334.         is_atomic = TRUE;        /* this block contains atomic objs */
  335.       } else {
  336.         is_atomic = FALSE;
  337.       }
  338.       if( sz > MAXOBJSZ ) {  /* 1 big object */
  339. #        ifdef SEPARATE_HEADERS
  340.           register bool mb = mark_bit_from_hdr(hhdr, HDR_WORDS);
  341. #        else
  342.           register bool mb = mark_bit(hbp, HDR_WORDS);
  343. #        endif
  344.               
  345. #           ifdef PRINTSTATS
  346.         now_count++;
  347. #           endif
  348. #           ifdef PRINTBLOCKS
  349.           GC_vprintf("%d(%c,%c)",sz, (is_atomic? 'a' : 'c'),
  350.                  mb ? 'n' : 'e' );
  351. #           endif
  352.         if (!mb) {
  353.             GC_mem_found += sz;
  354.                 SZ_LINK = GC_freeable_blocks;
  355.                 GC_freeable_blocks = hbp;
  356.         }  /* end if (empty) */
  357.       } else { /* group of smaller objects */
  358.         if (!(hb_tenured(hbp))) {
  359. #             ifdef PRINTSTATS
  360.         defer_count++;
  361. #             endif
  362.           if (is_atomic) {
  363.         SZ_LINK = areclaim_list[sz];
  364.         areclaim_list[sz] = hbp;
  365.           } else {
  366.         SZ_LINK = reclaim_list[sz];
  367.         reclaim_list[sz] = hbp;
  368.           }
  369.         } else {
  370. #               ifdef PRINTSTATS
  371.           skip_count++;
  372. #               endif
  373.         }
  374.       }
  375.       index--;
  376.       break;
  377.     default:
  378.       index -= hblkmap[index];
  379.       } /* end switch */
  380.     } /* end for */
  381. #   ifdef PRINTSTATS
  382.       GC_printf(
  383.     "Directly reclaimed %d blocks, deferred %d blocks, skipped %d blocks\n",
  384.     now_count, defer_count, skip_count);
  385. #   endif
  386. # undef GC_heapstart
  387. }
  388.  
  389. /* revoke all tenure */
  390. void GC_revoke_all_tenure()
  391. {
  392. register struct hblk *hbp;    /* ptr to current heap block        */
  393. register long index;
  394.  
  395.   /* Go through all heap blocks (in hblklist) and untenure everyone  */
  396.     hbp = (struct hblk *) (((long) GC_heaplim - 1) & ~(HBLKMASK-1));
  397.     index = hbp - (struct hblk *) GC_heapstart;
  398.     while (index >= 0) {
  399.       switch (hblkmap[index]) {
  400.         case HBLK_INVALID:
  401.           index--;
  402.           break;
  403.         case HBLK_VALID:
  404.           hbp = ((struct hblk *) GC_heapstart) + index;
  405.           hb_tenured(hbp) = 0;
  406.       index--;
  407.       break;
  408.     default:
  409.       index -= hblkmap[index];
  410.       } /* end switch */
  411.     } /* end while */
  412. }
  413.  
  414. /* Reclaim all objects in heap block pointed to by given    */
  415. /* reclaim list entry, and remove the block from the list.  */
  416. /* The block is assumed to contain atomic objects.        */
  417. /* Assumes GC_allocate_ml is not held.  Acquires it.        */
  418. /* Results are discarded if there is any possible        */
  419. /* interference with another thread.                */
  420. void GC_reclaim_atomic(rlp)
  421. struct hblk **rlp;    /* ptr to reclaim list entry        */
  422. {
  423.     register struct hblk * hbp;
  424.     register int word_no;       /* Number of word in block              */
  425.     register long i;
  426.     register word *p;           /* pointer to current word in block     */
  427.     register int mb;            /* mark bit of current word             */
  428.     int sz;                     /* size of objects in current block     */
  429.     word *plim;
  430.     int empty;                  /* empty & done with block => block empty */
  431.     struct obj *list;           /* list of free objects in block         */
  432.     struct obj *last;           /* last free object on list              */
  433.     register int words_found = 0;
  434.     unsigned long init_inval_counter;
  435.     bool busy;
  436. #   ifdef SEPARATE_HEADERS
  437.     register struct hblkhdr * hhdr;
  438. #   endif
  439.  
  440.     if (I_HOLD_ML(&GC_allocate_ml)) {
  441.         XR_Panic("GC_reclaim_atomic 0");
  442.     }
  443. #   ifdef GATHERSTATS
  444.     GC_reclaim_count++;
  445. #   endif
  446.  
  447.     XR_MonitorEntry(&GC_allocate_ml);
  448.     /* Free blocks waiting to be restored to free list while we're in control */
  449.         GC_free_blocks(A_FEW);
  450.     hbp = *rlp;
  451.     if (hbp == NIL) {
  452.         XR_MonitorExit(&GC_allocate_ml);
  453.         return;
  454.     }
  455. #   ifdef VISUALIZE
  456.     /* Make sure it's not dimmed */
  457.     displayAllocHblk(hbp, BYTES_TO_WORDS(HBLKSIZE));
  458. #   endif
  459.     * rlp = hb_sz_link(hbp);
  460.     init_inval_counter = GC_reclaim_inval_counter;
  461. #   ifdef SEPARATE_HEADERS
  462.     hhdr = HDR(hbp);
  463.     sz = -(hb_sz_from_hdr(hhdr));
  464.     busy = hb_busy_from_hdr(hhdr);
  465. #   else
  466.         sz = -(hb_sz(hbp));
  467.         busy = hb_busy(hbp);
  468. #   endif
  469.     if (busy) {
  470. XR_ConsoleMsg("Found busy block\n");
  471.     XR_MonitorExit(&GC_allocate_ml);
  472.         return;
  473.     }
  474. #   ifdef SEPARATE_HEADERS
  475.     hb_busy_from_hdr(hhdr) = TRUE;
  476. #   else
  477.         hb_busy(hbp) = TRUE;
  478. #   endif
  479.         
  480.     /* If this block looks like it will be tenured, avoid touching it. */
  481.       if (GC_hblk_probably_tenurable(hbp)
  482.           && GC_hblk_definitely_tenurable(hbp)) {
  483. #         ifdef GATHERSTATS
  484.         GC_tenure_count++;
  485. #         endif
  486.       hb_tenured(hbp) = 1;
  487.           XR_MonitorExit(&GC_allocate_ml);
  488.       return;
  489.       }
  490.       
  491.     XR_MonitorExit(&GC_allocate_ml);
  492.  
  493.     p = (word *)(hbp->hb_body);
  494.     word_no = ((word *)p) - ((word *)hbp);
  495.     plim = (word *)((((unsigned)hbp) + HBLKSIZE)
  496.        - WORDS_TO_BYTES(sz));
  497.  
  498.     last = (struct obj *)0;
  499.  
  500.     /* Look for first reclaimable object */
  501.     while( p <= plim && last == (struct obj *)0)  {
  502. #        ifndef SEPARATE_HEADERS
  503.           mb = mark_bit(hbp, word_no);
  504. #        else
  505.           mb = mark_bit_from_hdr(hhdr, word_no);
  506. #        endif
  507.  
  508.         if( mb ) {
  509. #               ifdef VISUALIZE
  510.             displayMark(p, sz);
  511. #               endif
  512.         p += sz;
  513.         } else {
  514.         words_found += sz;
  515.         /* word is available - put on list */
  516. #            ifdef DIRTY_BITS
  517.               /* We will write to this page.  This is likely to      */
  518.               /* generate a write fault.  Explicitly dirty the page  */
  519.               /* instead.                         */
  520.                 XR_PrepareForWriting(p);
  521. #            endif
  522.             ((struct obj *)p)->obj_link = (struct obj *)0;
  523.             last = list = ((struct obj *)p);
  524. #               ifdef VISUALIZE
  525.             displayFree(p, sz);
  526. #               endif
  527.         p += sz;
  528.         }
  529.         word_no += sz;
  530.     }
  531.  
  532.     /* Look for remaining reclaimable objects */
  533.     while( p <= plim )  {
  534. #        ifndef SEPARATE_HEADERS
  535.           mb = mark_bit(hbp, word_no);
  536. #        else
  537.           mb = mark_bit_from_hdr(hhdr, word_no);
  538. #        endif
  539.  
  540.         if( mb ) {
  541. #               ifdef VISUALIZE
  542.             displayMark(p, sz);
  543. #               endif
  544.         p += sz;
  545.         } else {
  546.         words_found += sz;
  547.         /* object is available - put on list */
  548.             ((struct obj *)p)->obj_link = list;
  549.             list = ((struct obj *)p);
  550. #               ifdef VISUALIZE
  551.             displayFree(p, sz);
  552. #               endif
  553.         p += sz;
  554.         }
  555.         word_no += sz;
  556.     }
  557.      
  558.  
  559.     empty = (p - (word *)(hbp->hb_body) == words_found);
  560.     /*
  561.      * if block has reachable words in it, we can't reclaim the
  562.      * whole thing so put list of free words in block back on
  563.      * free list for this size.
  564.      */
  565.  
  566. #    ifdef PRINTBLOCKS
  567.       GC_vprintf("%d(a,%c)",sz, (empty ? 'e' : 'n') );
  568. #    endif
  569.     XR_MonitorEntry(&GC_allocate_ml);
  570.     hb_busy(hbp) = FALSE;
  571.     if (init_inval_counter != GC_reclaim_inval_counter) {
  572. XR_ConsoleMsg("Found incremented reclaim counter\n");
  573.         XR_MonitorExit(&GC_allocate_ml);
  574.         return;
  575.     }
  576.     if (empty) {
  577.         hb_uninit(hbp) = 1;
  578.         /* remove this block from list of active blocks and free it */
  579.         {
  580.           GC_del_hblklist(hbp);  
  581.           GC_freehblk(hbp);
  582.           GC_mem_found += words_found;
  583.         }
  584.     } else { /* ! empty */
  585.       /* We checked for tenurable above, but only checked for definitely
  586.          tenurable if the block was probably tenurable.  Thus, it may happen
  587.          that a block is not probably tenurable, but against all probability
  588.          is indeed tenurable.  That's what this test here is for.
  589.          */
  590.           if (!TENURE(words_found)) {
  591.           last -> obj_link = aobjfreelist[sz];
  592.           aobjfreelist[sz] = list;
  593.           GC_mem_found += words_found;
  594.           } else {
  595.                   /* Throw away what we found, since we don't */
  596.           /* want to keep dirtying the page.          */
  597. #                 ifdef GATHERSTATS
  598.               GC_tenure_count++;
  599. #                 endif
  600. #                 ifdef VISUALIZE
  601.               dim_page(hbp);
  602. #                 endif
  603.           hb_tenured(hbp) = 1;
  604.           }
  605.           hb_last_reclaimed(hbp) = GC_gc_no;
  606.     }
  607.     XR_MonitorExit(&GC_allocate_ml);    
  608. }
  609.  
  610. /* Reclaim all objects in heap block pointed to by given    */
  611. /* reclaim list entry, and remove the block from the list.  */
  612. /* The block is assumed to contain composite objects.        */
  613. /* Assumes GC_allocate_ml is not held.  Acquires it.        */
  614. /* Results are discarded if there is any possible        */
  615. /* interference with another thread.                */
  616. void GC_reclaim_composite(rlp)
  617. struct hblk **rlp;    /* ptr to current heap block        */
  618. {
  619.     register struct hblk * hbp;
  620.     register int word_no;       /* Number of word in block              */
  621.     register long i;
  622.     register word *p;           /* pointer to current word in block     */
  623.     register int mb;            /* mark bit of current word             */
  624.     int sz;                     /* size of objects in current block     */
  625.     word *plim;
  626.     int empty;                  /* empty & done with block => block empty */
  627.     struct obj *list;           /* list of free objects in block         */
  628.     struct obj *last;           /* last free object on list              */
  629.     register int words_found = 0;
  630.     unsigned long init_inval_counter;
  631.     bool busy;
  632. #   ifdef SEPARATE_HEADERS
  633.     register struct hblkhdr * hhdr;
  634. #   endif
  635.  
  636. #   ifdef GATHERSTATS
  637.     GC_reclaim_count++;
  638. #   endif
  639.  
  640.     XR_MonitorEntry(&GC_allocate_ml);
  641.     /* Free blocks waiting to be restored to free list while we're in control */
  642.         GC_free_blocks(A_FEW);
  643.     hbp = *rlp;
  644.     if (hbp == NIL) {
  645.         XR_MonitorExit(&GC_allocate_ml);
  646.         return;
  647.     }
  648. #   ifdef VISUALIZE
  649.     /* Make sure it's not dimmed */
  650.     displayAllocHblk(hbp, BYTES_TO_WORDS(HBLKSIZE));
  651. #   endif
  652.     * rlp = hb_sz_link(hbp);
  653.     init_inval_counter = GC_reclaim_inval_counter;
  654. #   ifdef SEPARATE_HEADERS
  655.     hhdr = HDR(hbp);
  656.     sz = hb_sz_from_hdr(hhdr);
  657.     busy = hb_busy_from_hdr(hhdr);
  658. #   else
  659.         sz = hb_sz(hbp);
  660.         busy = hb_busy(hbp);
  661. #   endif
  662.     if (busy) {
  663. XR_ConsoleMsg("Found busy block\n");
  664.     XR_MonitorExit(&GC_allocate_ml);
  665.         return;
  666.     }
  667. #   ifdef SEPARATE_HEADERS
  668.     hb_busy_from_hdr(hhdr) = TRUE;
  669. #   else
  670.         hb_busy(hbp) = TRUE;
  671. #   endif
  672.  
  673.     /* If this block looks like it will be tenured, avoid touching it. */
  674.       if (GC_hblk_probably_tenurable(hbp)
  675.           && GC_hblk_definitely_tenurable(hbp)) {
  676. #         ifdef GATHERSTATS
  677.         GC_tenure_count++;
  678. #         endif
  679.       hb_tenured(hbp) = 1;
  680.           XR_MonitorExit(&GC_allocate_ml);
  681.       return;
  682.       }
  683.       
  684.     XR_MonitorExit(&GC_allocate_ml);
  685.  
  686.     p = (word *)(hbp->hb_body);
  687.     word_no = ((word *)p) - ((word *)hbp);
  688.     plim = (word *)((((unsigned)hbp) + HBLKSIZE)
  689.        - WORDS_TO_BYTES(sz));
  690.  
  691.     last = (struct obj *)0;
  692.  
  693.     /* Look for first reclaimable object */
  694.     while( p <= plim && last == (struct obj *)0)  {
  695. #        ifndef SEPARATE_HEADERS
  696.           mb = mark_bit(hbp, word_no);
  697. #        else
  698.           mb = mark_bit_from_hdr(hhdr, word_no);
  699. #        endif
  700.  
  701.         if( mb ) {
  702. #               ifdef VISUALIZE
  703.             displayMark(p, sz);
  704. #               endif
  705.         p += sz;
  706.         } else {
  707.         words_found += sz;
  708. #               ifdef VISUALIZE
  709.             displayFree(p, sz);
  710. #               endif
  711.         /* word is available - put on list */
  712. #            ifdef DIRTY_BITS
  713.               /* We will write to this page.  This is likely to      */
  714.               /* generate a write fault.  Explicitly dirty the page  */
  715.               /* instead.                         */
  716.                 XR_PrepareForWriting(p);
  717. #            endif
  718.             ((struct obj *)p)->obj_link = (struct obj *)0;
  719.             last = list = ((struct obj *)p);
  720.         /* Clear object, advance p to next object in the process */
  721.             i = (long)(p + sz);
  722.             p++; /* Skip link field */
  723.             while (p < (word *)i) {
  724.             *p++ = 0;
  725.             }
  726.         }
  727.         word_no += sz;
  728.     }
  729.  
  730.     /* Look for remaining reclaimable objects */
  731.     while( p <= plim )  {
  732. #        ifndef SEPARATE_HEADERS
  733.           mb = mark_bit(hbp, word_no);
  734. #        else
  735.           mb = mark_bit_from_hdr(hhdr, word_no);
  736. #        endif
  737.  
  738.         if( mb ) {
  739.         p += sz;
  740. #               ifdef VISUALIZE
  741.             displayMark(p, sz);
  742. #               endif
  743.         } else {
  744.         words_found += sz;
  745. #               ifdef VISUALIZE
  746.             displayFree(p, sz);
  747. #               endif
  748.         /* object is available - put on list */
  749.             ((struct obj *)p)->obj_link = list;
  750.             list = ((struct obj *)p);
  751.         /* Clear object, advance p to next object in the process */
  752.             i = (long)(p + sz);
  753.             p++; /* Skip link field */
  754.             while (p < (word *)i) {
  755.                *p++ = 0;
  756.             }
  757.         }
  758.         word_no += sz;
  759.     }
  760.      
  761.  
  762.     empty = (p - (word *)(hbp->hb_body) == words_found);
  763.     /*
  764.      * if block has reachable words in it, we can't reclaim the
  765.      * whole thing so put list of free words in block back on
  766.      * free list for this size.
  767.      */
  768.  
  769. #    ifdef PRINTBLOCKS
  770.       GC_vprintf("%d(c,%c)",sz, (empty ? 'e' : 'n') );
  771. #    endif
  772.     XR_MonitorEntry(&GC_allocate_ml);
  773.     hb_busy(hbp) = FALSE;
  774.     if (init_inval_counter != GC_reclaim_inval_counter) {
  775. XR_ConsoleMsg("Found incremented reclaim counter\n");
  776.         XR_MonitorExit(&GC_allocate_ml);
  777.         return;
  778.     }
  779.     if (empty) {
  780.         /* Clear words at beginning of objects */
  781.         /* Since most of it is already cleared */
  782.         p = (word *)(hbp->hb_body);
  783.         plim = (word *)((((unsigned)hbp) + HBLKSIZE)
  784.                - WORDS_TO_BYTES(sz));
  785.         while (p <= plim) {
  786.           *p = 0;
  787.           p += sz;
  788.         }
  789.         hb_uninit(hbp) = 0;
  790.  
  791.         /* remove this block from list of active blocks and free it */
  792.         {
  793.           GC_del_hblklist(hbp);  
  794.           GC_freehblk(hbp);
  795.           GC_mem_found += words_found;
  796.         }
  797.  
  798.     } else { /* ! empty */
  799.       /* Add to the appropriate free list, unless it's too full    */
  800.       /* We claim that we don't lose much if this gets interrupted */
  801.       /* in the middle.                                            */
  802.       /* We checked for turable above, but only checked for definitely
  803.          tenurable if the block was probably tenurable.  Thus, it may happen
  804.          that a block is not probably tenurable, but against all probability
  805.          is indeed tenurable.  That's what this test here is for.
  806.          */
  807.         if (!TENURE(words_found)) {
  808.           last -> obj_link = objfreelist[sz];
  809.           objfreelist[sz] = list;
  810.           GC_mem_found += words_found;
  811.           /* ...and here is where we need to fluff up the mark bits for
  812.              two-collection survival policy */
  813.         } else {
  814.                   /* Throw away what we found, since we don't */
  815.           /* want to keep dirtying the page.          */
  816. #                 ifdef GATHERSTATS
  817.               GC_tenure_count++;
  818. #                 endif
  819. #                 ifdef VISUALIZE
  820.               dim_page(hbp);
  821. #                 endif
  822.           hb_tenured(hbp) = 1;
  823.         }
  824.         hb_last_reclaimed(hbp) = GC_gc_no;
  825.     }
  826.     XR_MonitorExit(&GC_allocate_ml);
  827. }
  828.  
  829. /* Return an entire small object block to the free memory pool.     */
  830. /* it had better be empty.  Otherwise we make no assumptions.        */
  831. /* We try not to touch the block itself.                */
  832. void GC_reclaim_entire_block(hbp)
  833. register struct hblk *hbp;
  834. {
  835.     short sz = hb_sz(hbp);
  836.     
  837.     if (hb_busy(hbp)) {
  838. XR_ConsoleMsg("GC_reclaim_entire_block encountered busy\n");
  839.     /* Some one is still busy reclaiming this from a previous     */
  840.     /* collection cycle, and may be writing a free list in it.    */
  841.     /* He'll eventually look at GC_reclaim_inval_counter and    */
  842.     /* discard it.  Then we'll catch it the next time.        */
  843.     return;
  844.     }
  845.     if (sz < 0) sz = -sz;
  846.     hb_uninit(hbp) = 1;
  847.     GC_del_hblklist(hbp);
  848.     GC_freehblk(hbp);
  849.     GC_mem_found += (BODY_SZ - (BODY_SZ % sz));
  850. }
  851.  
  852. /* Check whether a heap block is definitely empty.       */
  853. /* Hbp points to a block containing small objects.       */
  854. /* May (with tiny probability) identify an empty     */
  855. /* block as nonempty.                     */
  856. bool GC_hblk_empty(hbp)
  857. register struct hblk *hbp;    /* ptr to current heap block        */
  858. {
  859.     register long * m;
  860.     register long * marks = hb_marks(hbp);
  861.     register long * mark_lim = marks + MARK_BITS_SZ;
  862.  
  863.     /* Make a quick attempt at ignoring bogus mark bits at the beginning. */    
  864.       if (HDR_WORDS >= 16) {
  865.         if (HDR_WORDS >= 32) {
  866.             marks++;
  867.         } else {
  868.             *marks &= 0xffff0000;
  869.         }
  870.       }
  871.     for (m = marks; m < mark_lim; m++) {
  872.         if (*m) return(FALSE);
  873.     }
  874.  
  875.     return(TRUE);
  876. }
  877.  
  878. /* Check whether a heap block is likely to be tenurable.     */
  879. /* Hbp points to a block containing small objects.           */
  880. /* Only a hint.  May err on either side.             */
  881. bool GC_hblk_probably_tenurable(hbp)
  882. register struct hblk *hbp;    /* ptr to current heap block        */
  883. {
  884.     register int sz;            /* size of objects in current block     */
  885. #   define  start_word_no HDR_WORDS
  886.     register int nobjs;
  887.     register int middle_obj;
  888.     register int beginning_obj;
  889.  
  890.     sz = hb_sz(hbp);
  891.     if (sz < 0) sz = -sz;
  892.  
  893.     switch (sz) {
  894.         case 1:
  895.           nobjs = (BYTES_TO_WORDS(HBLKSIZE) - start_word_no);
  896.           beginning_obj = start_word_no + ((nobjs - 1) >> 2);
  897.           break;
  898.         case 2:
  899.           nobjs = (BYTES_TO_WORDS(HBLKSIZE) - start_word_no)/2;
  900.           beginning_obj = start_word_no + (((nobjs - 1) >> 2) << 1);
  901.           break;
  902.         case 4:
  903.           nobjs = (BYTES_TO_WORDS(HBLKSIZE) - start_word_no)/4;
  904.           beginning_obj = start_word_no + ((nobjs - 1) & ~3);
  905.           break;
  906.         case 6:
  907.           nobjs = (BYTES_TO_WORDS(HBLKSIZE) - start_word_no)/6;
  908.           beginning_obj = start_word_no + ((nobjs - 1) >> 2) * 6;
  909.           break;
  910.         case 8:
  911.           nobjs = (BYTES_TO_WORDS(HBLKSIZE) - start_word_no)/8;
  912.           beginning_obj = start_word_no + (((nobjs - 1) >> 2) << 3);
  913.           break;
  914.         case 16:
  915.           nobjs = (BYTES_TO_WORDS(HBLKSIZE) - start_word_no)/16;
  916.           beginning_obj = start_word_no + (((nobjs - 1) >> 2) << 4);
  917.           break;
  918.         default:
  919.           nobjs = IDIV((BYTES_TO_WORDS(HBLKSIZE) - start_word_no),sz);
  920.           beginning_obj = start_word_no + ((nobjs - 1) >> 2) * sz;
  921.     }
  922.  
  923.     if (!mark_bit(hbp, beginning_obj)) return(FALSE);
  924.     
  925.     middle_obj = /* start_word_no + ((nobjs - 1) >> 1) * sz */
  926.                  (beginning_obj << 1) - start_word_no;
  927.     if (!mark_bit(hbp, middle_obj)) return(FALSE);
  928.     
  929.     return(TRUE);
  930. }
  931.  
  932. /* Check whether a heap block is definitely tenurable.       */
  933. /* Hbp points to a block containing small objects.           */
  934. /* We do not dirty the heap block in question.               */
  935. bool GC_hblk_definitely_tenurable(hbp)
  936. register struct hblk *hbp;    /* ptr to current heap block        */
  937. {
  938.     register int word_no;       /* Number of word in block              */
  939.     register int mb;            /* mark bit of current word             */
  940.     register int sz;            /* size of objects in current block     */
  941. #   define  start_word_no HDR_WORDS
  942.     int nobjs;
  943.     register int n_empty = 0;     /* Number of reclaimable words. */
  944. #   ifdef SEPARATE_HEADERS
  945.     register struct hblkhdr * hhdr = HDR(hbp);
  946. #   endif
  947.  
  948.     sz = hb_sz(hbp);
  949.     if (sz < 0) sz = -sz;
  950.  
  951.     nobjs = IDIV((BYTES_TO_WORDS(HBLKSIZE) - start_word_no), sz);
  952.  
  953.     word_no = start_word_no + (nobjs - 1) * sz;
  954.  
  955.     /* Count empty words. */
  956.     while( word_no >= start_word_no )  {
  957. #        ifndef SEPARATE_HEADERS
  958.           mb = mark_bit(hbp, word_no);
  959. #        else
  960.           mb = mark_bit_from_hdr(hhdr, word_no);
  961. #        endif
  962.         if( ! mb ) {
  963.         n_empty += sz;
  964.         }
  965.         word_no -= sz;
  966.     }
  967.         return(TENURE(n_empty));
  968. }
  969.  
  970. @
  971.